package _08_DFS_BFS;

import java.util.ArrayList;
import java.util.List;

public class _22_括号生成复习 {

    public static void main(String[] args) {

        _22_括号生成复习 v = new _22_括号生成复习();

        List<String> strings = v.generateParenthesis(3);

        System.out.println(strings);

    }

    // 左括号数量
    private int left;

    // 右括号数量
    private int right;

    // 左括号
    private static final char LEFT_STR = '(';

    // 右括号
    private static final char RIGHT_STR = ')';

    // 结果集
    private List<String> results = new ArrayList<>();

    private int n;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        // dfs获取结果
        dfs(new char[n << 1]);
        return results;
    }

    private void dfs(char[] chars) {
        if (right == n) {
            // 括号选择完成
            results.add(new String(chars));
            return;
        }
        if (left < n) {
            // 可以选择左括号
            chars[left + right] = LEFT_STR;
            left++;
            dfs(chars);
            // 回溯
            left--;
        }
        if (left > right) {
            // 可以能选择右括号
            chars[left + right] = RIGHT_STR;
            right++;
            dfs(chars);
            // 回溯
            right--;
        }

    }

}
